//
//  1035. 不相交的线.swift
//  LeetCodeTrain
//
//  Created by rjb on 2021/6/25.
//  Copyright © 2021 rjb. All rights reserved.
//

import Foundation
class Solution1035 {
    // 本题实际上就是最长公共子序列问题
    func maxUncrossedLines(_ nums1: [Int], _ nums2: [Int]) -> Int {
        var dp = Array(repeating: Array(repeating: 0, count: nums2.count + 1), count: nums1.count + 1)
        for i in 1...nums1.count {
            for j in 1...nums2.count {
                if nums1[i - 1] == nums2[j - 1] {
                    dp[i][j] = dp[i - 1][j - 1] + 1
                } else {
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
                }
            }
        }
        return dp[nums1.count][nums2.count]
    }
    static func test() {
        let solution = Solution1035()
        let nums1 = [1,4,2]
        let nums2 = [1,2,4]
       let result =  solution.maxUncrossedLines(nums1, nums2)
        print(result)
    }
}
